With the recent advancement of communication information technology, important information is being provided through various types of communication media including wired, wireless, and satellite communications. However, it is necessary that such important information is transmitted in a most secured manner.
Various kinds of cipher protocols, such as secret-key cryptosystem or public-key cryptosystem, have been developed and used for transferring the information in a secured manner. The secret-key cryptosystem, which is a type of the common key block cipher, has proved to be most suitable for high-speed cipher communication.
A variety of cipher algorithms have been proposed as the conventional common key block cipher. Most of such algorithms adopt a simple and repetitive structure referred to as the Feistel structure. In an internal portion of this Feistel structure, which is also referred to as F-function, non-linear functions referred to as S-boxes are aligned, and a combination of outputs is dispersed by a linear function in most of the cases. The internal structure referred to as the F-function is generally known as SPN (Substitution Permutation Network) structure.
It is by no means easy to design the S-boxes that form the security core of the common key block cipher. Also, as more kinds of S-boxes are used, a larger memory capacity is required to store the S-boxes. Hence, in the general common key block cipher, in order to reduce the development costs of the S-boxes and memory capacity and thereby simplify the structure thereof, the same S-box is used repetitively or the S-boxes having the same input size or output size are reused.
Because the input bit number in the common key block cipher is generally 64 or 128, S-boxes having the 2n-bit input are used when using the S-boxes of the same size without any duplication. However, the S-boxes actually have either the 4-bit or 8-bit input due to restriction of implementation.
That is, because the S-boxes are the portions that are most frequently referred to in the cipher apparatus, they are most likely to affect the cipher rate. For this reason, it is desirable to design in such a manner that the entire table representing the S-boxes is enclosed in a fastest referable storage device (generally, a primary cache memory) in the computer. However, if the input bit number of the S-boxes increases, the table size gradually increases exponentially. Because there is an upper limit of the practically usable table size, if reference should be made to a table exceeding the capacity of the storage device, the access rate drops more than the numerical value. In view of the foregoing, only the 4-bit input and 8-bit input are the alternatives for the S-boxes having the 2n-input to avoid disadvantages in the as implemented state.
The memory capacity of the present day computers is increasing year after year. Although it may be too early to adopt the S-boxes having the 16-bit input, it cannot be said that the memory source of the computers is fully utilized by the S-boxes having the 8-bit input.
In other words, S-boxes having the input of the fewer bit number can be enclosed in the primary cache memory in computers of almost any type. In this case, however, the total number of the S-boxes increases, and so does the number of times for referring to the S-boxes, thereby posing a problem that the performance rate is reduced.
Conversely, S-boxes having the input of the greater bit number can reduce the number of times for referring to the S-boxes, but the size of the table forming the S-boxes is increased. Hence, the S-boxes cannot be enclosed in the primary cache memory, and have to be installed in other storage device having the lower referring rate. For this reason, each reference to the table takes longer, thereby causing a problem that an overall performance rate is reduced.
In view of the foregoing, it is quite important how an optimal S-box that meets the computer performance should be selected when designing the common key block cipher having the S-boxes.